package ch05;

/**
 * @author zzMh
 * @Description TODO
 */
class Trie {
    private Node root;

    public Trie() {
        root = new Node();
    }

    private class Node {
        Node[] childs = new Node[26];
        boolean isLeaf;

        private boolean containsKey(char c) {
            return childs[c - 'a'] != null;
        }
    }

    public void insert(String word) {
        Node node = root;
        int len = word.length();
        for (int i = 0; i < len; i++) {
            char c = word.charAt(i);
            if (!node.containsKey(c)) {
                node.childs[c - 'a'] = new Node();
            }
            node = node.childs[c - 'a'];
        }
        node.isLeaf = true;
    }

    private Node searchPre(String word) {
        int len = word.length();
        Node node = root;
        for (int i = 0; i < len; i++) {
            char c = word.charAt(i);
            if (!node.containsKey(c))
                return null;
            node = node.childs[c - 'a'];
        }
        return node;
    }


    public boolean search(String word) {
        Node node = searchPre(word);
        if (node == null) return false;
        return node.isLeaf;
    }


    public boolean startsWith(String prefix) {
        return searchPre(prefix) != null;
    }
}
